/*
 * @lc app=leetcode.cn id=1508 lang=cpp
 *
 * [1508] 子数组和排序后的区间和
 */

// @lc code=start
class Solution
{
public:
    struct RangeUnit
    {
        RangeUnit(int i, int j, int sum) : i(i), j(j), sum(sum) {}

        int i, j, sum;
    };

    struct cmp
    {
        bool operator()(const RangeUnit &a, const RangeUnit &b)
        {
            return a.sum > b.sum;
        }
    };

    int rangeSum(vector<int> &nums, int n, int left, int right)
    {
        priority_queue<RangeUnit, vector<RangeUnit>, cmp> pq;
        int modNum = 1e9 + 7;
        for (int i = 0; i < n; i++)
        {
            pq.push(RangeUnit(i, i, nums[i]));
        }

        int ans = 0;
        for (int i = 1; i <= right; i++)
        {
            RangeUnit curr = pq.top();
            pq.pop();
            if (i >= left)
            {
                ans += curr.sum;
                ans %= modNum;
            }
            if (curr.j + 1 < n)
            {
                pq.push(RangeUnit(curr.i, curr.j + 1, curr.sum + nums[curr.j + 1]));
            }
        }
        return ans;
    };
};
// @lc code=end
